|
Bézout's identity (also called Bézout's lemma) is a theorem in the elementary theory of numbers: let ''a'' and ''b'' be nonzero integers and let ''d'' be their greatest common divisor. Then there exist integers ''x'' and ''y'' such that : In addition, * the greatest common divisor ''d'' is the smallest positive integer that can be written as * every integer of the form is a multiple of the greatest common divisor ''d''. The integers ''x'' and ''y'' are called Bézout coefficients for (''a'', ''b''); they are not unique. A pair of Bézout coefficients can be computed by the extended Euclidean algorithm. If both ''a'' and ''b'' are nonzero, the extended Euclidean algorithm produces one of the two pairs such that and Bézout's lemma is true in any principal ideal domain, but there are integral domains in which it is not true. ==Structure of solutions== When one pair of Bézout coefficients (''x'', ''y'') has been computed (e.g., using extended Euclidean algorithm), all pairs can be represented in the form : where is an arbitrary integer and the fractions simplify to integers. Among these pairs of Bézout coefficients, exactly two of them satisfy : This relies on a property of Euclidean division: given two integers ''c'' and ''d'', if ''d'' does not divide ''c'', there is exactly one pair such that and , and another one such that and . The Extended Euclidean algorithm always produces one of these two minimal pairs. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Bézout's identity」の詳細全文を読む スポンサード リンク
|